package structure.array;


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 地址：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
 * <p>
 * 题目：剑指 Offer 42. 连续子数组的最大和
 * <p>
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * <p>
 * 要求时间复杂度为O(n)。
 * <p>
 * 示例1:
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释:连续子数组[4,-1,2,1] 的和最大，为6。
 */
public class Leetcode_Sword_Offer_42 {
    public static void main(String[] args) {

        int[] input = new int[]{3, 2, 1};
        int[] input1 = new int[]{0, 1, 2, 1};

        int leastNumbers = maxSubArray(input);
            System.out.println(leastNumbers);


    }



    /**
     * 解法1：
     * 思路： 动态规划
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * <p>
     * 执行结果：通过
     * 执行用时：8 ms, 在所有 Java 提交中击败了63.54%的用户
     * 内存消耗：39.4 MB, 在所有 Java 提交中击败了87.98%的用户
     * <p>
     * 可以优化的地方在哪里？
     * 利用堆排序
     *
     * @return
     */
    public static int maxSubArray(int[] nums) {
        int prev = 0, max = nums[0];
        for (int num : nums) {
            prev = Math.max(prev + num, num);
            max = Math.max(max, prev);
        }
        return max;
    }
}
